/**
 * @program: LeetCode
 * @description: LeetCode : 112. 路径总和
 * @author: WXY
 * @create: 2023-01-02 15:48
 * @Version 1.0
 **/
public class num112_hasPathSum {
    public static boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null) return false;
        Info ans = process(root, targetSum);
        return ans.isEqual;
    }

    private static Info process(TreeNode root, int targetSum) {
        if (root == null) return new Info(false);
        if (root.right == null && root.left == null) {
            if (root.val == targetSum) return new Info(true);
            return new Info(false);
        }
        int curVal = targetSum - root.val;
        Info leftInfo = process(root.left, curVal);
        Info rightInfo = process(root.right, curVal);
        boolean isEqual = (leftInfo != null ? leftInfo.isEqual : false) || (rightInfo != null ? rightInfo.isEqual : false);
        return new Info(isEqual);
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(5);
        head.left = new TreeNode(4);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(11);
        head.left.left.left = new TreeNode(7);
        head.left.left.right = new TreeNode(2);
        head.right.left = new TreeNode(13);
        head.right.right = new TreeNode(4);
        head.right.right.right = new TreeNode(1);
        boolean b = hasPathSum(head, 22);
        System.out.println(b);
    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static class Info {
        boolean isEqual;

        public Info(boolean isEqual) {
            this.isEqual = isEqual;
        }
    }
}
